package com.fyl.basic_algorithm.backtrack;

/**
 * @Description: 假设正则表达式中只包含“*”和“?”这两种通配符，
 * “*”匹配任意多个（大于等于 0 个）任意字符，“?”匹配零个或者一个任意字符。
 * @author:fyl
 * @date 2021/4/18 17:38
 * @Modified By:
 * @Modified Date:
 */
public class Pattern {
    private boolean matched = false;
    private char[] pattern; //正则表达式
    private int plen;  //正则表达式长度

    public Pattern(boolean matched, int plen) {
        this.matched = matched;
        this.plen = plen;
    }

    /**
     * @param text 文本串
     * @param tlen 文本串长度
     * @return
     */
    public boolean match(char[] text, int tlen) {
        matched = false;
        rmatch(0,0,text,tlen);
        return matched;
    }

    /**
     * 匹配的回溯算法
     * 调用方式  rmatch(0,0,text,tlen)
     * @param ti 文本串指针
     * @param pj 正则表达式指针
     * @param text 文本串
     * @param tlen 文本串长度
     */
    private void rmatch(int ti, int pj, char[] text, int tlen) {
        if (matched) return;  //
        if (pj == plen) {  //正则表达式到结尾
            if (ti == tlen) matched = true;  //文本串到结尾
        }
        if (pattern[pj] == '*') { //*匹配任意个字符
            for (int k = 0; k <= tlen - ti; k++) {
                rmatch(ti + k, pj + 1, text, tlen);
            }
        } else if (pattern[pj] == '?') {  //？匹配0个或者1个字符
            rmatch(ti, pj + 1, text, tlen);
            rmatch(ti + 1, pj + 1, text, tlen);
        } else if (ti < tlen && pattern[pj] == text[ti]) {  //纯字符匹配才行
            rmatch(ti + 1, pj + 1, text, tlen);
        }
    }
}
